package solutions.leetcode.normal;

import solutions.lib.BaseSolution;

import java.util.LinkedList;
import java.util.List;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/combination-sum-iii/">216. 组合总和 III</a>
 */
public class Solution216 extends BaseSolution {

    public List<List<Integer>> combinationSum3(int k, int n) {
        boolean[] flag = new boolean[9];
        List<List<Integer>> rst = new LinkedList<>();
        check(rst, flag, n, k, 0);
        return rst;
    }

    private void check(List<List<Integer>> rst, boolean[] flag, int target, int num, int now) {
        if (num == 0) {
            if (target == 0) {
                rst.add(genrateByFlag(flag));
            }
            return;
        }
        if (num < 0 || now > target || now >= flag.length) {
            return;
        }
        flag[now] = true;
        check(rst, flag, target - now - 1, num - 1, now + 1);
        flag[now] = false;
        check(rst, flag, target, num, now + 1);
    }

    private List<Integer> genrateByFlag(boolean[] flag) {
        List<Integer> list = new LinkedList<>();
        for (int i = 0, size = flag.length; i < size; i++) {
            if (flag[i]) {
                list.add(i + 1);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        Solution216 solution = new Solution216();
        solution.combinationSum3(7, 3);
    }
}